// $Id: memdriver.c,v 1.6 2006-10-30 17:50:24 nicolasw Exp $
#include "memdriver.h"

#include <malloc.h>
#include <assert.h>
#include <stdio.h> // debugging printfs

#define MAX(x,y) ((x>y)?(x):(y))
#define IMPL(x,y) (!(x) || (y))
#define INV_NODE(c) (IMPL(c, c->rtag && c->vtag && 0<c->size))
// local invariant for node i and i+1 (previous and current respectively)
// this implies tag(i)<tag(i+1) ie, locally unique and sorted
#define INV_NODE_R(p,c) (IMPL(p && c, p->rtag + p->size <= c->rtag))
#define INV_NODE_V(p,c) (IMPL(p && c, p->vtag + p->size <= c->vtag))

typedef struct node_s node_s;
struct node_s // linked list node
{
	void *rtag; // real tag as coming from trace
	void *vtag; // virtual tag given by heapmanager
	size_t size; // span
	node_s *next_r; // thread to next strictly increasing real tag
	node_s *next_v; // thread to next strictly increasing virtual tag
};

struct memdriver_s // here it is the hidden structure
{
	heapmanager_s *hm; // heapmanager being driven, just to read parameters
	node_s *head_r; // head of sorted by real tag list
	node_s *head_v; // head of sorted by virtual tag list
	// stats
	unsigned int nmalloc, nfree; // number of mallocs and free
	unsigned long int malloc_size_acc; // accumulated size of mallocs
	size_t malloc_size_max; // max malloc size
	bool dirtystat; // stat cache is dirty?
	unsigned int nholes; // number of holes
	unsigned int mean_hole; // average of holes size
	float int_frag; // ratio of internal fragmentation
	
};

static void md_getstats(memdriver_s *this); // get&cache stats
#ifdef DEBUG
static void md_print_list_r(const memdriver_s *this);
#endif

// Creates the initial Memory Driver structure
memdriver_s *md_create(heapmanager_s *hm)
{
	memdriver_s *result = NULL;
	assert(hm);
	
	result = calloc(sizeof(memdriver_s),1);
	if (result) {
		result->hm = hm;
		result->head_r = NULL;
		result->head_v = NULL;
		result->dirtystat = true;
		result->nmalloc = result->nfree = 0;
		result->nholes = 0;
		result->mean_hole = 0;
		result->int_frag = 0.0;
	}

	return result;
}


// Restores memory to a _real_ HM!
void md_destroy(memdriver_s *this)
{
	node_s *prev = NULL, *curr = NULL;
	assert(this);
	
	#ifdef DEBUG
	md_print_list_r(this); // print leftovers
	#endif
	
	curr = this->head_r; // traversing through head_v should be the same
	while (curr)
	{
		assert(INV_NODE(curr));
		prev = curr;
		curr = curr->next_r;
		free(prev);
	}
	free(this);
	return;
}


// Drives the trace malloc
bool md_malloc(memdriver_s *this, void *rtag, void *vtag, size_t size)
{
	node_s *prev_r = NULL, *curr_r = NULL;
	node_s *new = NULL;
	node_s *prev_v = NULL, *curr_v = NULL;

	assert(this);
	assert(rtag && vtag && 0<size);
	assert(hm_offset(this->hm) <= vtag && vtag < hm_offset(this->hm)+hm_mem_size(this->hm));
	this->dirtystat = true; // invalid chached stats

	// search real tag linked list position
	curr_r = this->head_r;
	while (curr_r && !(IMPL(prev_r, prev_r->rtag<rtag) && IMPL(curr_r, rtag<=curr_r->rtag)))
	{
		assert(INV_NODE(curr_r));
		assert(INV_NODE_R(prev_r,curr_r));
		prev_r = curr_r;
		curr_r = curr_r->next_r;
	}
	// it is fresh new
	assert(IMPL(curr_r, curr_r->rtag!=rtag));
	// we are in the middle
	assert(IMPL(prev_r, prev_r->rtag<rtag) && IMPL(curr_r, rtag<curr_r->rtag));
	// it fits in the middle
	assert(IMPL(prev_r, prev_r->rtag+prev_r->size <= rtag));
	assert(IMPL(curr_r, rtag+size <= curr_r->rtag));

	// search virtual tag linked list position
	curr_v = this->head_v;
	while (curr_v && !(IMPL(prev_v, prev_v->vtag<vtag) && IMPL(curr_v, vtag<=curr_v->vtag)))
	{
		assert(INV_NODE(curr_v));
		assert(INV_NODE_V(prev_v,curr_v));
		prev_v = curr_v;
		curr_v = curr_v->next_v;
	}
	// it is fresh new
	assert(IMPL(curr_v, curr_v->vtag!=vtag));
	// we are in the middle
	assert(IMPL(prev_v, prev_v->vtag<vtag) && IMPL(curr_v, vtag<curr_v->vtag));
	// it fits in the middle
	assert(IMPL(prev_v, prev_v->vtag+prev_v->size <= vtag));
	assert(IMPL(curr_v, vtag+size <= curr_v->vtag));

	// prepare  and fill in new node
	new = calloc(sizeof(node_s),1);
	new->rtag = rtag;
	new->vtag = vtag;
	new->size = size;
	new->next_r = curr_r;
	new->next_v = curr_v;

	// chain it in both sorted linked lists

	// depending on (prev,curr) 4 cases to thread, they collapse to two
	if (prev_r) // last (T,F) or in the middle (T,T)
	{
		prev_r->next_r = new;
	} else // empty (F,F) or first (F,T)
	{
		this->head_r = new;
	}
	// note this last irregularity can be avoided if "head" is a node.
	// think Daniel Moisset used this trick.

	if (prev_v) // last or middle
	{
		prev_v->next_v = new;
	} else // empty or first
	{
		this->head_v = new;
	}
	
	// stats
	this->nmalloc++;
	this->malloc_size_acc += size;
	this->malloc_size_max = MAX(size, this->malloc_size_max);
	
	return true; //TODO: return something different than true if hm is giving troubles, perhaps some kind of enum!?
}


void *md_free(memdriver_s *this, void *rtag)
{
	void *vtag = NULL;
	node_s *prev_r = NULL, *curr_r = NULL;
	node_s *prev_v = NULL, *curr_v = NULL;

	assert(this);
	assert(rtag);
	this->dirtystat = true;

	// get prev_r and curr_r
	curr_r = this->head_r;
	while (!(IMPL(prev_r, prev_r->rtag<rtag) && IMPL(curr_r,rtag<=curr_r->rtag)))
	{
		assert(INV_NODE(curr_r));
		assert(INV_NODE_R(prev_r,curr_r));
		prev_r = curr_r;
		curr_r = curr_r->next_r;
	}
	// module non nullness of prev and curr, here we have
	//	prev->rtag < rtag <= curr->rtag
	assert((IMPL(prev_r, prev_r->rtag<rtag) && IMPL(curr_r,rtag<=curr_r->rtag)));
	// actually got it
	assert(curr_r && curr_r->rtag == rtag);

	vtag = curr_r->vtag;
	assert(vtag);

	// get prev_v and curr_v
	curr_v = this->head_v;
	while (!(IMPL(prev_v, prev_v->vtag<vtag) && IMPL(curr_v,vtag<=curr_v->vtag)))
	{
		assert(INV_NODE(curr_v));
		assert(INV_NODE_V(prev_v,curr_v));
		prev_v = curr_v;
		curr_v = curr_v->next_v;
	}
	// module non nullness of prev and curr, here we have
	//	prev->rtag < rtag <= curr->rtag
	assert((IMPL(prev_v, prev_v->vtag<vtag) && IMPL(curr_v,vtag<=curr_v->vtag)));
	// actually got it
	assert(curr_v && curr_v->vtag == vtag);

	assert(curr_r == curr_v); //both point the same thingy

	// unchain it from both
	if (prev_r) prev_r->next_r = curr_r->next_r;
	else this->head_r = curr_r->next_r;
	if (prev_v) prev_v->next_v = curr_v->next_v;
	else this->head_v = curr_v->next_v;

	free(curr_r);
	
	// stats
	this->nfree++;

	return vtag;
}


unsigned int md_nmalloc(const memdriver_s *this)
{
	assert(this);
	return this->nmalloc;
}


unsigned int md_nfree(const memdriver_s *this)
{
	assert(this);
	return this->nfree;
}


size_t md_malloc_size_avg(const memdriver_s *this)
{
	assert(this);
	if (0<this->nmalloc)
		return (size_t)(this->malloc_size_acc/this->nmalloc);
	else
		return 0;
}


size_t md_malloc_size_max(const memdriver_s *this)
{
	assert(this);
	return this->malloc_size_max;
}


unsigned int md_nholes(memdriver_s *this)
{
	assert(this);
	if (this->dirtystat)
		md_getstats(this);
	return this->nholes;
}


unsigned int md_mean_hole(memdriver_s *this)
{
	assert(this);
	if (this->dirtystat)
		md_getstats(this);
	return this->mean_hole;
}


float md_int_frag(memdriver_s *this)
{
	assert(this);
	if (this->dirtystat)
		md_getstats(this);
	return this->int_frag;
}


static void md_getstats(memdriver_s *this)
{
	node_s *curr_v = NULL, *prev_v = NULL;
	unsigned int nholes = 0;
	unsigned long int holes_size = 0L;
	unsigned long int mem_alloc = 0L, mem_used = 0L;
	
	assert(this);
	curr_v = this->head_v;
	prev_v = NULL;
	if (curr_v && hm_offset(this->hm) < curr_v->vtag) { // inital hole
		nholes++;
		holes_size += curr_v->vtag - hm_offset(this->hm);
	}
	while (curr_v) {
		mem_alloc += curr_v->size;
		if (curr_v->size%hm_block_size(this->hm)==0) {
			mem_used += curr_v->size;
		} else {
			mem_used += curr_v->size + hm_block_size(this->hm) - curr_v->size%hm_block_size(this->hm);
		}
		assert(mem_used % hm_block_size(this->hm) == 0); // always multiple of blocksize
		prev_v = curr_v;
		curr_v = curr_v->next_v;
		if (prev_v && curr_v && prev_v->vtag+prev_v->size < curr_v->vtag) {
			nholes++;
			holes_size += curr_v->vtag - (prev_v->vtag+prev_v->size);
		}
	}
	if (prev_v && prev_v->vtag < hm_offset(this->hm)+hm_mem_size(this->hm)) { // final hole
		nholes++;
		holes_size += hm_offset(this->hm)+hm_mem_size(this->hm) - prev_v->vtag;
	}
	if (!prev_v && !curr_v) { // empty memory
		assert(nholes==0 && holes_size==0);
		nholes++;
		holes_size += hm_mem_size(this->hm);
	}
	this->nholes = nholes;
	this->mean_hole = (unsigned int)(holes_size/nholes);
	assert(mem_alloc<=mem_used);
	if (0<mem_used) {
		this->int_frag = 1.0 - (mem_alloc/mem_used);
	} else {
		this->int_frag = 0.0;
	}
	this->dirtystat = false; //fresh new stats
}


#ifdef DEBUG
void md_print_list_r(const memdriver_s *this)
{
	node_s *curr_r = NULL, *prev_r = NULL;
	assert(this);

	printf("DEBUG: ");
	curr_r = this->head_r;
	while (curr_r)
	{
		assert(INV_NODE(curr_r));
		assert(INV_NODE_R(prev_r,curr_r));
		printf("[%p,%i) ", curr_r->rtag, curr_r->size);
		prev_r = curr_r;
		curr_r = curr_r->next_r;
	}
	printf("\n");
	fflush(0);
}
#endif
